package airthmetic.exercise.unionfind;

// 并查集
//提供四个操作：
// 1、初始化构建
// 2、查找
// 3、合并
// 4、获取集合个数
public class UnionFind {

    private int count = 0;
    private int[] father;

    public UnionFind(int num){
        father = new int[num];
        for(int i=0; i<num; i++){
            father[i] = i;
        }
        count = num;
    }

    public int find(int point){
        if(father[point] == point){
            return point;
        }
        father[point] = find(father[point]);

        return find(father[point]);
    }

    public int union(int pointQ, int pointP){
        int q = find(pointQ);
        int p = find(pointP);
        if (q == p){
            return q;
        }
        // q指向p
        father[q] = p;
        count--;
        return p;
    }

    public int count(){
        return this.count;
    }

    public static void main(String[] args) {
        UnionFind unionFind = new UnionFind(5);
        System.out.println(unionFind.count());
        unionFind.union(2,3);
        System.out.println(unionFind.count());
        System.out.println(unionFind);

    }


}
